//1.最小值两边必定有一边有序，要么两边都有序
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;

            if(nums[mid] == target)
                return mid;

            // 左半段有序
            if(nums[left] <= nums[mid]) {    //为什么不是<号，因为最坏情况left==mid,比如[4,1],target=1,如果<判定，那么4<4不成立，进入else部分，逻辑就错了
                if(nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            
            /*
            对于无重复的旋转数组，任意一次二分都存在且仅存在两种情况：

                nums[left] <= nums[mid]（左半段有序）

                nums[left] > nums[mid]（左半段断裂，右半段必然有序，即 nums[mid] <= nums[right]）
                右半段有序   ---等价于else if (nums[left] > nums[mid]) 等价于 else if (nums[right] >= nums[mid]
            */
            else {
                if(nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }
};
